package link;

import beans.ListNode;
import utils.AlgUtils;

import java.util.Stack;

import static utils.AlgUtils.printListNodes;

/**
 * @Author: pengfei.hpf
 * @Date: 2020/1/27
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 *
 * 示例 1:
 *
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 * 示例 2:
 *
 * 输入: 1->1->1->2->3
 * 输出: 2->3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class DeleteDuplicates {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode node = head.next;
        Stack<ListNode> stack = new Stack<>();
        ListNode newHead = null;
        ListNode lastNode = null;
        stack.push(head);
        while(!stack.isEmpty()){
            if (node == null || stack.peek().val != node.val) {
                if(stack.size() == 1){
                    ListNode temp = stack.pop();
                    if(newHead == null){
                        newHead = temp;
                        lastNode = newHead;
                    } else {
                        lastNode.next = temp;
                        lastNode = temp;
                    }
                    lastNode.next = null;
                } else {
                    stack.removeAllElements();
                }
            }
            if(node != null) {
                stack.push(node);
                node = node.next;
            }
        }
        return newHead;
    }

    public static void main(String[] args){
        ListNode head = AlgUtils.createListNode(new int[]{1,1,1,2,3,3,4,5,5});
        ListNode newHead = (new DeleteDuplicates()).deleteDuplicates(head);
        printListNodes(newHead);
    }
}
